package com.suxin.algorithm.graph;

import lombok.AllArgsConstructor;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * @author Tang
 * @classname DFS
 * @description [ 深度优先 ]
 * @date 2023/1/10 16:10
 */
public class DFS {

    @AllArgsConstructor
    static class Points{
        private final Integer x;
        private final Integer y;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Points points = (Points) o;
            return x.equals(points.x) && y.equals(points.y);
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    /**
     * 地图
     */
    private static final int[][] MAPS = new int[][]{
            {0,0,1,0},
            {0,0,0,0},
            {0,0,1,0},
            {0,1,0,0},
            {0,0,0,0}
    };

    /**
     * 标记数组
     */
    private static final boolean[][] MARK = new boolean[5][4];

    static {
        MARK[0][0] = true;
    }

    /**
     * 上下左右
     */
    private static final int[][] POSITION = new int[][]{
            {0, 1}, {1, 0}, {0, -1}, {-1, 0}
    };

    private Integer minStep = Integer.MAX_VALUE;

    private final List<Points> ways = new ArrayList<>();

    /**
     * 思路：一条路走到底，不行就回溯。
     * @param x
     * @param y
     * @param point
     * @param step
     */
    public void dfs(int x,int y,Points point,int step) {
        if (x == point.x && y == point.y) {
            minStep = Math.min(step, minStep);
            System.out.print("满足条件的路径:");
            ways.forEach(item -> System.out.print(item.x + "," + item.y + "-->"));
            System.out.println(point.x + "," + point.y);
            return;
        }
        ways.add(new Points(x, y));
        for (int[] ints : POSITION) {
            int newX = x + ints[0];
            int newY = y + ints[1];
            if (newX >= 0 && newX < MARK.length && newY >= 0
                    && newY < MARK[0].length && !MARK[newX][newY]) {
                // 障碍物
                if (MAPS[newX][newY] == 1) {
                    continue;
                }
                MARK[newX][newY] = true;
                // 递归
                dfs(newX, newY, point,step + 1);
                // 回溯
                MARK[newX][newY] = false;
                ways.remove(new Points(newX, newY));
            }
        }
    }

    public static void main(String[] args) {
        DFS dfs = new DFS();
        dfs.dfs(0,0,new Points(3,2),0);
        System.out.println("minStep:"+dfs.minStep);
    }

}
